The primary responsibility of an Internet Service Provider (ISP) is to provide transit service from its set of customers to the remainder of the Internet and to bring traffic from its own upstream providers and peers destined to its customers. The interface from the ISP to the customers, upstream providers, and peers is through a set of border routers of the ISP. Currently, a border gateway protocol (BGP) allows border gateways (“border router” and “border gateway” will be used interchangeably) to be selected to carry transit traffic flows.
This responsibility is balanced with an objective of the ISP to minimize the resources used on its network in carrying transit traffic. The ISP wishes to get traffic “on its way” toward its ultimate destination as quickly as possible.
A poorly designed selection of border routers for the flows of traffic through the ISP can result in numerous problems. Ingress and/or egress traffic from/to neighbors may exceed the capacity of the selected border routers and its links, causing the ISP to fail to meet its responsibility. On the other side, underutilization of the potential capacity at border routers, or carrying traffic across the ISP network longer than necessary results in inefficient use of costly resources of the ISP.
Unfortunately, ISPs today have few tools or algorithms to help with this problem. Policies governing inter-domain routing and border router selection are arrived at manually through applying intuition, ad-hoc methods and constant tuning.
Accordingly, what is needed in the art is a better way to determine a selection of border routers used for ingress and egress of transit traffic that reduces, and ideally minimizes, provider network utilization and better balances the load of traffic flows from neighbors across the selected border routers by respecting capacity constraints.